// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <stddef.h>

#include <list>

#include "base/logging.h"
#include "media/base/test_random.h"
#include "media/blink/lru.h"
#include "testing/gtest/include/gtest/gtest.h"

// Range of integer used in tests below.
// We keep the integers small to get lots of re-use of integers.
const int kTestIntRange = 16;

namespace media {

class LRUTest;

class SimpleLRU {
public:
    void Insert(int x)
    {
        DCHECK(!Contains(x));
        data_.push_back(x);
    }

    void Remove(int x)
    {
        for (std::list<int>::iterator i = data_.begin(); i != data_.end(); ++i) {
            if (*i == x) {
                data_.erase(i);
                DCHECK(!Contains(x));
                return;
            }
        }
        LOG(FATAL) << "Remove non-existing element " << x;
    }

    void Use(int x)
    {
        if (Contains(x))
            Remove(x);
        Insert(x);
    }

    bool Empty() const { return data_.empty(); }

    int Pop()
    {
        DCHECK(!Empty());
        int ret = data_.front();
        data_.pop_front();
        return ret;
    }

    int Peek()
    {
        DCHECK(!Empty());
        return data_.front();
    }

    bool Contains(int x) const
    {
        for (std::list<int>::const_iterator i = data_.begin(); i != data_.end();
             ++i) {
            if (*i == x) {
                return true;
            }
        }
        return false;
    }

    size_t Size() const { return data_.size(); }

private:
    friend class LRUTest;
    std::list<int> data_;
};

class LRUTest : public testing::Test {
public:
    LRUTest()
        : rnd_(42)
    {
    }

    void Insert(int x)
    {
        truth_.Insert(x);
        testee_.Insert(x);
        Compare();
    }

    void Remove(int x)
    {
        truth_.Remove(x);
        testee_.Remove(x);
        Compare();
    }

    void Use(int x)
    {
        truth_.Use(x);
        testee_.Use(x);
        Compare();
    }

    int Pop()
    {
        int truth_value = truth_.Pop();
        int testee_value = testee_.Pop();
        EXPECT_EQ(truth_value, testee_value);
        Compare();
        return truth_value;
    }

    void Compare()
    {
        EXPECT_EQ(truth_.Size(), testee_.Size());
        auto testee_iterator = testee_.lru_.rbegin();
        for (const auto truth : truth_.data_) {
            EXPECT_TRUE(testee_iterator != testee_.lru_.rend());
            EXPECT_EQ(truth, *testee_iterator);
            ++testee_iterator;
        }
        EXPECT_TRUE(testee_iterator == testee_.lru_.rend());
    }

    bool Empty() const
    {
        EXPECT_EQ(truth_.Empty(), testee_.Empty());
        return truth_.Empty();
    }

    bool Contains(int i) const
    {
        EXPECT_EQ(truth_.Contains(i), testee_.Contains(i));
        return testee_.Contains(i);
    }

    void Clear()
    {
        while (!Empty())
            Pop();
    }

    int Peek()
    {
        EXPECT_EQ(truth_.Peek(), testee_.Peek());
        return testee_.Peek();
    }

protected:
    media::TestRandom rnd_;
    SimpleLRU truth_;
    media::LRU<int> testee_;
};

TEST_F(LRUTest, SimpleTest)
{
    Insert(1); // 1
    Insert(2); // 1 2
    Insert(3); // 1 2 3
    EXPECT_EQ(1, Peek());
    EXPECT_EQ(1, Pop()); // 2 3
    EXPECT_EQ(2, Peek());
    Use(2); // 3 2
    EXPECT_EQ(3, Peek());
    EXPECT_EQ(3, Pop()); // 2
    EXPECT_EQ(2, Pop());
    EXPECT_TRUE(Empty());
}

TEST_F(LRUTest, UseTest)
{
    EXPECT_TRUE(Empty());
    // Using a value that's not on the LRU adds it.
    Use(3); // 3
    EXPECT_EQ(3, Peek());
    Use(5); // 3 5
    EXPECT_EQ(3, Peek());
    EXPECT_TRUE(Contains(5));
    Use(7); // 3 5 7
    EXPECT_EQ(3, Peek());
    EXPECT_TRUE(Contains(7));
    // Using a value that's alraedy on the LRU moves it to the top.
    Use(3); // 5 7 3
    EXPECT_EQ(5, Peek());
    EXPECT_TRUE(Contains(5));
    EXPECT_EQ(5, Pop()); // 7 3
    EXPECT_FALSE(Contains(5));
    EXPECT_EQ(7, Peek());
    EXPECT_TRUE(Contains(7));
    EXPECT_TRUE(Contains(3));
    Use(9); // 7 3 9
    EXPECT_EQ(7, Peek());
    // Using the same value again has no effect.
    Use(9); // 7 3 9
    EXPECT_EQ(7, Peek());
    Use(3); // 7 9 3
    EXPECT_EQ(7, Pop());
    EXPECT_EQ(9, Pop());
    EXPECT_EQ(3, Pop());
    EXPECT_TRUE(Empty());
}

TEST_F(LRUTest, RemoveTest)
{
    Insert(5); // 5
    Insert(4); // 5 4
    Insert(3); // 5 4 3
    Insert(2); // 5 4 3 2
    Insert(1); // 5 4 3 2 1
    EXPECT_EQ(5, Peek());
    Remove(5); // 4 3 2 1
    EXPECT_EQ(4, Peek());
    Remove(1); // 4 3 2
    EXPECT_EQ(4, Peek());
    Remove(3); // 4 2
    EXPECT_EQ(4, Pop());
    EXPECT_EQ(2, Pop());
    EXPECT_TRUE(Empty());
}

TEST_F(LRUTest, RandomTest)
{
    for (int j = 0; j < 100; j++) {
        Clear();
        for (int i = 0; i < 1000; i++) {
            int value = rnd_.Rand() % kTestIntRange;
            switch (rnd_.Rand() % 3) {
            case 0:
                if (!Empty())
                    Pop();
                break;

            case 1:
                Use(value);
                break;

            case 2:
                if (Contains(value)) {
                    Remove(value);
                } else {
                    Insert(value);
                }
                break;
            }
            if (HasFailure()) {
                return;
            }
        }
    }
}

} // namespace media
